"""
树和堆
二叉树的存储
    ~ 连续存储：按照完全二叉树将树节点编号，编号为i的节点对应列表下标为i的元素
    ~ 离散存储：通过对象引用维持树节点之间的关系，可以使用碎片内存
"""
from collections import namedtuple


class BiTreeNode:
    """二叉树节点"""

    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


class BinarySearchTree:
    """二叉排序树（二叉搜索树）
    特点：左子树上所有节点都小于根节点，右子树上所有节点都大于跟节点，
    通过中序遍历（左-根-右）就可以获得有序的序列
    """

    def __init__(self):
        self.root = None

    def insert(self, node):
        """插入节点"""
        if not self.root:
            self.root = node
        else:
            current_node = self.root
            while current_node:
                parent_node = current_node
                if node.data <= current_node.data:
                    current_node = current_node.left
                elif node.data > current_node.data:
                    current_node = current_node.right
            if node.data <= parent_node.data:
                parent_node.left = node
            else:
                parent_node.right = node

    @property
    def pre_visitor(self):
        """先序遍历（根-左-右）"""
        yield from self._pre_order_visit(self.root)

    @property
    def in_visitor(self):
        """中序遍历（左-根-右）"""
        yield from self._in_order_visit(self.root)
    
    @property
    def post_visitor(self):
        """后序遍历（左-右-根）"""
        yield from self._post_order_visit(self.root)
    
    def _pre_order_visit(self, node):
        if node:
            yield node.data
            yield from self._pre_order_visit(node.left)
            yield from self._pre_order_visit(node.right)
    
    def _in_order_visit(self, node):
        if node:
            yield from self._in_order_visit(node.left)
            yield node.data
            yield from self._in_order_visit(node.right)
    
    def _post_order_visit(self, node):
        if node:
            yield from self._post_order_visit(node.left)
            yield from self._post_order_visit(node.right)
            yield node.data


nums = [55, 32, 55, 18, 40, 32, 68, 95, 72, 20, 20]
tree = BinarySearchTree()
for num in nums:
    tree.insert(BiTreeNode(num, None, None))
sorted_nums = [num for num in tree.in_visitor]
print(sorted_nums)
